#include "../include/huffmanCodes.h"
#include "../include/huffmanNode.h" // 包含HuffmanNode结构体的声明
#include "../include/huffmanTree.h"
#include <iostream>
#include <string>
#include <cstring>

using namespace std;


#define MAX 1000

typedef struct Elemtype
{
    char data[MAX];
} Elemtype;

typedef struct Queue
{
    Elemtype data[MAX];
    int front, rear;
} Queue;

void init(Queue* q)
{
    q->front = -1;
    q->rear = -1;
}

int enqueue(Queue* q, Elemtype e)
{
    if ((q->rear + 1) % MAX == q->front) // 队列已满
    {
        printf("队列已满！\n");
        return -1; // 返回错误代码
    }
    q->rear = (q->rear + 1) % MAX;
    strcpy(q->data[q->rear].data, e.data);
    return 0; // 返回成功代码
}

void dequeue(Queue* q)
{
    if (q->front == q->rear) // 队列为空
    {
        printf("队列为空！\n");
    }
    else
    {
        printf("%s\n", q->data[q->front+1].data);
        q->front = (q->front + 1) % MAX;
    }
}

int empt(Queue* q)
{
    return q->front == q->rear; // 队列为空的条件
}

void getword(Queue* q, char inp[])
{
    int i = 0, j = 0;
    Elemtype teminp;
    for (; inp[i] != '\0'; i++)
    {
        if (inp[i] >= 32 && inp[i] <= 47 || inp[i] >= 58 && inp[i] <= 64 || inp[i] >= 91 && inp[i] <= 96 || inp[i] >= 123 && inp[i] <= 126) // 判断是否为符号
        {
            teminp.data[j] = '\0';
            if (j > 0) // 确保不是空字符串才入队
                enqueue(q, teminp);
            j = 0;
        }
        else if ((inp[i] >= 'a' && inp[i] <= 'z') || (inp[i] >= 'A' && inp[i] <= 'Z'))
        {
            teminp.data[j] = inp[i];
            j++;
        }
        else
        {
            teminp.data[j] = '\0';
            j = 0;
        }
    }
    // 处理最后一个单词（如果有的话）
    if (j >= 0)
        enqueue(q, teminp);
    
}

std::unordered_map<std::string, int> calculateFrequency(Queue *q, std::unordered_map<std::string, int> freqMap) 
{
    int frequency[MAX] = {0};

    int size = (q->rear + 1) % MAX;
    for (int i = 0; i < size; i++) {
        int count = 1;
        for (int j = i + 1; j < size; j++) {
            if (strcmp(q->data[(q->front + i) % MAX].data,
                       q->data[(q->front + j) % MAX].data) == 0) {
                count++;
                
            }
        }
        frequency[i] = count;
    }

    for (int i = 1; i < size; i++) {
        int printed = 0;
        for (int j = 0; j < i; j++) {
            if (strcmp(q->data[(q->front + i) % MAX].data,
                       q->data[(q->front + j) % MAX].data) == 0) {
                printed = 1;
                break;
            }
        }
        if (!printed) {
            std::string wordString = std::string{ q->data[(q->front + i) % MAX].data };
            freqMap[wordString] = frequency[i] * wordString.length(); 
            // printf("'%s' : %d 次\n",
            //        q->data[(q->front + i) % MAX].data,
            //        frequency[i]);
        }
    }
    return freqMap;
}

/*void kmp(Queue q, char inp[])
{
    int i = 0, j = -1; // i 为当前匹配位置，j 为前缀后缀匹配位置
    while (i < strlen(inp))
    {
        if (j == -1 || strcmp(inp,q.data[j].data) != 0)
        {
            i++;
            j++;
        }
        else
        {
            j = q.data[j].data[0];
        }
        // 匹配成功
        if (q.data[j].data[0] == '\0')
        {
            printf("%s\n", q.data[j].data);
            i--; // 回溯
            j = j - 1;
        }
}
*/

std::unordered_map<std::string, int> getfr(std::string text)
{
    std::unordered_map<std::string, int> freqMap;
    // for (char ch : text) {
    //     freqMap[std::string{ ch }]++;
    // }
    std::string currentChar;
    bool hasMultiByte = false;
    for (size_t i = 0; i < text.size(); ) {
        unsigned char c = text[i];
        // 如果是ASCII字符
        if ((c & 0x80) == 0) {
            currentChar = c;
            i++;
        } else {
            hasMultiByte = true;
            // 处理多字节字符（如中文）
            size_t len = 1;
            if ((c & 0xE0) == 0xC0) len = 2;
            else if ((c & 0xF0) == 0xE0) len = 3;
            else if ((c & 0xF8) == 0xF0) len = 4;
            currentChar = text.substr(i, len);
            i += len;
        }
        freqMap[currentChar]++;
    }

    // 如果文本中没有多字节字符
    Queue q; 
    init(&q);
    text = text + " ";
    char * inp = new char[text.length() + 2];
    std::strcpy(inp, text.c_str() );
    // fgets(inp, MAX, stdin);
    getword(&q, inp);
    freqMap = calculateFrequency(&q, freqMap);
    // freqMap[std::string{ "thi" }] = 10; //指定一个字符串的频率
    delete[] inp;
    return freqMap;
}

void generateCodes(HuffmanNode* root, const std::string& str, std::unordered_map<std::string, std::string>& huffmanCode) {
    // 如果根节点为空，则直接返回
    if (root == nullptr)
        return;

    // 如果当前节点没有左子节点和右子节点，表示是叶子节点
    if (!root->left && !root->right) {
        // 将字符和对应的哈夫曼编码存入哈希表中
        huffmanCode[root->ch] = str;
    }

    // 递归处理左子树，并在当前编码后添加'0'
    generateCodes(root->left, str + "0", huffmanCode);
    // 递归处理右子树，并在当前编码后添加'1'
    generateCodes(root->right, str + "1", huffmanCode);
}
// std::string encodeLongestMatch(const std::string& text, int startIndex, std::unordered_map<std::string, std::string>& huffmanCode) {
//     std::string encodedStr;
//     int textLength = text.length();
    
//     while (startIndex < textLength) {
//         // 尝试匹配最长字符串
//         for (int len = textLength - startIndex; len > 0; --len) {
//             std::string substr = text.substr(startIndex, len);
//             if (huffmanCode.count(substr)) {
//                 // 如果找到了匹配的字符串，则使用其哈夫曼编码
//                 encodedStr += huffmanCode[substr];
//                 startIndex += len; // 更新起始索引
//                 break; // 跳出内层循环，继续查找下一个匹配项
//             }
//         }
        
//         // 如果没有找到任何匹配项，则编码单个字符（作为回退策略）
//         if (startIndex < textLength) {
//             encodedStr += huffmanCode[string(1, text[startIndex++])];
//         }
//     }
    
//     return encodedStr;
// }
std::string encodeLongestMatch(const std::string& text, int startIndex, std::unordered_map<std::string, std::string>& huffmanCode) {
    std::string encodedStr;
    int textLength = text.length();
    
    while (startIndex < textLength) {
        bool matched = false;
        
        // 尝试匹配最长字符串
        for (int len = textLength - startIndex; len > 0; --len) {
            std::string substr = text.substr(startIndex, len);
            if (huffmanCode.count(substr)) {
                // 如果找到了匹配的字符串，则使用其哈夫曼编码
                encodedStr += huffmanCode[substr];
                startIndex += len; // 更新起始索引
                matched = true;
                break; // 跳出内层循环，继续查找下一个匹配项
            }
        }
        
        // 如果没有找到任何匹配项，则编码单个字符（作为回退策略）
        if (!matched && startIndex < textLength) {
            // 处理多字节字符
            unsigned char c = text[startIndex];
            size_t len = 1;
            if ((c & 0xE0) == 0xC0) len = 2;
            else if ((c & 0xF0) == 0xE0) len = 3;
            else if ((c & 0xF8) == 0xF0) len = 4;
            std::string singleChar = text.substr(startIndex, len);
            encodedStr += huffmanCode[singleChar];
            startIndex += len;
        }
    }
    
    return encodedStr;
}

//编码
/**
 * @brief 编码字符串
 *
 * 根据给定的哈夫曼编码表，将输入的字符串进行编码。
 *
 * @param text 待编码的字符串
 * @param huffmanCode 哈夫曼编码表，字符到编码字符串的映射
 *
 * @return 编码后的字符串
 */
std::string encode(const std::string& text, std::unordered_map<std::string, std::string>& huffmanCode) {
    // std::string encodedStr;
    // for (char ch : text) {
    //     encodedStr += huffmanCode[string {ch}];
    // }
    // return encodedStr;
    return encodeLongestMatch(text, 0, huffmanCode);
}
//解码
/**
 * @brief 解码二叉树表示的字符串
 *
 * 根据给定的二叉树和编码字符串，解码出原始字符串。
 *
 * @param root 二叉树的根节点指针
 * @param encodedStr 编码后的字符串
 *
 * @return 解码后的原始字符串
 */
std::string decode(HuffmanNode* root, const std::string& encodedStr) {
    std::string decodedStr;
    HuffmanNode* current = root;
    for (char bit : encodedStr) {//循环遍历字符串
        if (bit == '0') {
            current = current->left;
        } else {
            current = current->right;
        }

        if (!current->left && !current->right) {//如果当前节点是叶子节点，则将其字符添加到解码字符串中，并重置当前节点为根节点，开始新一轮的搜索，直到搜索到叶子节点为止。
            decodedStr += current->ch;
            current = root;
        }
    }
    return decodedStr;
}
